前置知识
Matrix-Tree定理
对于无向图 $G$，定义其度数矩阵 $D$
$$
\left[
\begin{matrix}
deg_1 & 0 & 0 & \cdots & 0 \\
0 & deg_2 & 0 & \cdots & 0 \\
0 & 0 & deg_3 & \cdots & 0 \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
0 & 0 & 0 & 0 & deg_n
\end{matrix}
\right]
$$
定义其邻接矩阵 $C$
$$
\left[
\begin{matrix}
0 & a_{1,2} & a_{1,3} & \cdots & a_{1,n} \\
a_{2,1} & 0 & a_{2,3} & \cdots & a_{2,n} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_{n,1} & a_{n,2} & a_{n,3} & a_{n,4} & 0
\end{matrix}
\right]
$$
其中 $a_{i, j} \in \{0, ~1\}$
定于其的基尔霍夫矩阵 $L(G) = D - C$，则有 $L(G)$ 的任意代数余子式即为无向图 $G$ 的生成树个数
至于求代数余子式则任意删去第 $i$ 行 $i$ 列高斯消元得其斜上三角矩阵最后即有 $ans = \sum\limits_i a_{i,i}$
至于证明就留坑吧
拓展
- 带权图生成树：定义一棵生成树的权值为边权之积，求解所有生成树的权值之和。 将 $D$ 中的 $deg_i$ 改为连接其的点的权值和，再令 $C$ 中 $a_{i, j} = w_{i, j}$ （$w_{i, j}$ 为边权），最后Matrix-Tree定理即可
- 有向图的生成树形图计数：我们将度数矩阵改为入度，邻接矩阵改为有向边的邻接矩阵，以 $p$ 为根的树形图个数是去掉 $p$ 行 $p$ 列后做行列式得的答案
多项式求逆 $O (n^2)$
于是我先会 $O (n \log n)$ 再会 $O (n^2)$ 我也很绝望啊
令 $C(x) = A(x)B(x) \pmod p$，首先有 $C_0 = A_0B_0 = 1 \pmod p$ （此处表示在 $\mod p$ 意义下，然后以 $C_1$ 为例，则有 $C_1 = A_0B_1 + A_1B_0 = 0 \pmod p$，可解得 $B_1 = - \frac{A_1B_0}{A_0}$，其它同理
题解
首先对于 $(w_1 + w_2 + w_3 + \wedge ~+ w_n)^k = \sum\prod\limits_{i = 1}^n w_{\forall}$
那么可以联想到有标号的整数拆分，那么即可将每条边的边权设为原边权的 EGF，即 $value = \sum\limits_{n \ge 0} w^n\frac{x^n}{n!}$ （$w$ 为原边权），接下来Matrix-Tree即可
最后得到一个多项式 $G(x)$，答案即为 $ans = G_k \cdot fact_k$
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
| #include <iostream>
#include <cstdio>
#include <cstring>
#define MOD 998244353
using namespace std;
typedef long long LL;
const int MAXN = 30 + 10;
const int MAXK = 30 + 10;
LL power (LL x, int p) {
LL cnt = 1;
while (p) {
if (p & 1)
cnt = cnt * x % MOD;
x = x * x % MOD;
p >>= 1;
}
return cnt;
}
LL invf[MAXN];
int N, k;
LL map[MAXN][MAXN][MAXK]= {0};
LL res[MAXN]= {0};
LL temp[MAXK]= {0}, tmp[MAXK]= {0};
void multiply (LL* a, LL* b, LL* ret) {
memset (temp, 0, sizeof (temp));
for (int i = 0; i <= k; i ++)
for (int j = 0; j <= i; j ++)
temp[i] = (temp[i] + a[j] * b[i - j] % MOD) % MOD;
memcpy (ret, temp, sizeof (temp));
}
void inv (LL* a, LL* ret) {
for (int i = 0; i <= k; i ++)
temp[i] = tmp[i] = 0;
temp[0] = power (a[0], MOD - 2);
for (int i = 1; i <= k; i ++)
tmp[i] = a[i] * temp[0] % MOD;
for (int i = 1; i <= k; i ++)
for (int j = 1; j <= i; j ++)
temp[i] = (temp[i] - tmp[j] * temp[i - j] % MOD + MOD) % MOD;
memcpy (ret, temp, sizeof (temp));
}
LL ret[MAXK]= {0};
void Gauss () {
res[0] = 1;
for (int i = 1; i < N; i ++) {
multiply (map[i][i], res, res);
inv (map[i][i], ret);
for (int j = i; j < N; j ++)
multiply (map[i][j], ret, map[i][j]);
memset (map[i][i], 0, sizeof (map[i][i]));
map[i][i][0] = 1;
for (int j = i + 1; j < N; j ++)
for (int t = N - 1; t >= i; t --) {
multiply (map[i][t], map[j][i], ret);
for (int l = 0; l <= k; l ++) {
map[j][t][l] = (map[j][t][l] - ret[l] + MOD) % MOD;
}
}
}
}
int getnum () {
int num = 0;
char ch = getchar ();
while (! isdigit (ch))
ch = getchar ();
while (isdigit (ch))
num = (num << 3) + (num << 1) + ch - '0', ch = getchar ();
return num;
}
int main () {
N = getnum (), k = getnum ();
invf[0] = invf[1] = 1;
for (int i = 2; i <= k; i ++)
invf[i] = (- MOD / i + MOD) % MOD * invf[MOD % i] % MOD;
for (int i = 1; i <= k; i ++)
invf[i] = invf[i] * invf[i - 1] % MOD;
for (int i = 1; i <= N; i ++)
for (int j = 1; j <= N; j ++) {
LL delta = getnum ();
if (j <= i) continue;
LL pow = 1;
for (int l = 0; l <= k; l ++) {
LL value = pow * invf[l] % MOD;
map[i][j][l] = map[j][i][l] = (- value + MOD) % MOD;
map[i][i][l] = (map[i][i][l] + value) % MOD;
map[j][j][l] = (map[j][j][l] + value) % MOD;
pow = pow * delta % MOD;
}
}
Gauss ();
LL ans = res[k];
for (int i = 1; i <= k; i ++)
ans = ans * i % MOD;
cout << ans << endl;
return 0;
}
|
